Large and small comparison with many things → Fennic tree
I want to know the number of items that satisfy the condition by comparing the size of N items and the number of items that satisfy the condition.
O(N) when large and small comparisons are made for each one.
However, O(NQ) is sometimes too slow, especially in cases where many queries are issued.
If we put N things in the Fennic tree, we can get the number of things that satisfy the condition in logarithmic order by taking the range sum ---
This page is auto-translated from /nishio/多くのものと大小比較→フェニック木. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I'm very happy to spread my thought to non-Japanese readers.